/**
 * 求公共祖先问题：
 * 一个使用顺序存储的树，求节点i和节点j的公共祖先的值
 * 首先明确，两个节点必定有公共父节点，最坏的情况就是根节点
 * 
 * 求公共祖先的步骤如下：
 * 若i>j，则i所在的层数大于或等于j所在的层数，此时i的双亲节点为i/2
 * 若i/2=j，则i/2是i和j的公共祖先
 * 若i/2!=j,则令i=i/2然后以这个节点作为起点开始递归
 * 
 * 若j>i说明j所在的层数大于等于i所在的层数，j的双亲为j/2
 * 若j/2=i,则j/2是i和j的公共祖先
 * 若j/2!=i 则令j=j/2
 */

#include"SqTree.h"
int ancestor(SqTree t,int i,int j){
    if(t[i]!=-1&&t[j]!=-1){
        while (i!=j)
        {
            if(i>j){
                i=i/2;
            }else{
                j=j/2;
            }
        }
        return t[i];
        
    }
}